package fangpian.leecode

//4. 寻找两个正序数组的中位数 [困难]

//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
//算法的时间复杂度应该为 O(log (m+n)) 。
fun main() {
    // 补充完整
    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        val num1Size = nums1.size

        var ttt: IntArray? = null
        if (nums1.isEmpty()) {
            ttt = nums2
        } else if (nums2.isEmpty()) {
            ttt = nums1
        }

        // 如果是偶数 则 找到 中间两个数
        if (ttt != null) {
            if (ttt.size % 2 == 0) {
                val end = ttt.size - 1
                val zhong = (ttt[end / 2] + ttt[end / 2 + 1]) / 2.0
                return zhong
            }
            // 如果是 奇数 则不用额外计算
            else {
                return ttt[ttt.size / 2].toDouble()
            }
        }

        val num2Size = nums2.size
        val numSum = num1Size + num2Size
        var i = 0
        var j = 0
        // 当找到第 end / 2 的数之后判断是偶数则再找一个数并取平均
        val zhong = (numSum - 1) / 2
        if (numSum % 2 == 0) {
            // 找到中间两个数
            var x = 0
            var num = Double.MIN_VALUE
            var prev = num
            while (x <= zhong + 1) {
                if (i == num1Size) {
                    prev = num
                    num = nums2[j++].toDouble()
                } else if (j == num2Size) {
                    prev = num
                    num = nums1[i++].toDouble()
                } else if (nums1[i] > nums2[j]) {
                    prev = num
                    num = nums2[j++].toDouble()
                } else {
                    prev = num
                    num = nums1[i++].toDouble()
                }
                x++
            }
            return (prev + num) / 2.0
        } else {
            // 找到中间一个数
            var x = 0
            var num = Double.MIN_VALUE
            while (x <= zhong) {
                if (i == num1Size) {
                    num = nums2[j++].toDouble()
                } else if (j == num2Size) {
                    num = nums1[i++].toDouble()
                } else if (nums1[i] > nums2[j]) {
                    num = nums2[j++].toDouble()
                } else {
                    num = nums1[i++].toDouble()
                }
                x++
            }
            return num
        }
    }

    // 方法一 先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。然后根据奇数，还是偶数，返回中位数。

    // 方法二
    println(findMedianSortedArrays(intArrayOf(1, 2), intArrayOf(3, 4)) == 2.5)
    println(findMedianSortedArrays(intArrayOf(1, 3), intArrayOf(2)) == 2.0)
    println(findMedianSortedArrays(intArrayOf(2), intArrayOf()) == 2.0)
    println(findMedianSortedArrays(intArrayOf(3), intArrayOf(-2, -1)) == -1.0)

    //
//    val num1 = intArrayOf(1, 2)
//    // 如果是偶数 则 找到 中间两个数
//    if (num1.size % 2 == 0) {
//        val end = num1.size - 1
//        val zhong = (num1[end / 2] + num1[end / 2 + 1]) / 2.0
//        println(zhong)
//    }
//    // 如果是 奇数 则不用额外计算
//    else {
//        println(num1[num1.size / 2])
//    }
}